package chapter01.problem10;

import java.util.LinkedList;

/**
 * 最大值减去最小值小于等于num的子数组的个数
 * @author llw
 *
 */
public class Problem10 {

	public static int findNumOfSubArray(int[] a, int num) {
		int columnNum = a.length;
		if (columnNum <= 0) {
			return 0;
		}
		//保存最大值
		LinkedList<Integer> maxDeque = new LinkedList<Integer>();
		//保存最小值
		LinkedList<Integer> minDeque = new LinkedList<Integer>();
		int account = 0;
		int j = 0, i = 0;
		while (i < columnNum) {
			while (j < columnNum) {
				//如果队列后面的值对应的数组中的值大于等于当前下标对应的值，则弹出，否则加入 
				//这里有等于符号！！！因为下面有个if，如果满足条件就跳出循环，而j的值还没有增加，
				//因此再进行处理的话j对应的值要重新处理一下
				while (!minDeque.isEmpty() && a[minDeque.getLast()] >= a[j]) {
					minDeque.pollLast();
				}
				minDeque.add(j);
				while (!maxDeque.isEmpty() && a[maxDeque.getLast()] <= a[j]) {
					maxDeque.pollLast();
				}
				maxDeque.add(j);
				if (a[maxDeque.getFirst()] - a[minDeque.getFirst()] > num)
					break;
				//j++放在最下面，如果上面的情况满足了，就要退出循环，并且要从min的双端队列或者max的双端队列中取出一个，
				//因此可能取出之后上面的式子依然满足，所以要重新处理一下j
				j++;
			}
			account += j - i;
			//打印所有的情况
			for (int k = i; k < j; ++k) {
				for (int t = i; t <= k; ++t)
					System.out.print(a[t]);
				System.out.println();
			}
			//弹出
			if(minDeque.getFirst() == i)
				minDeque.removeFirst();
			if(maxDeque.getFirst() == i)
				maxDeque.removeFirst();
			++i;
		}
		return account;
	}

	public static void main(String[] args) {
		int[] a={1,2,3,4};
		int num = Problem10.findNumOfSubArray(a, 1);
		System.out.println("满足要求的分组数有： "+num);
	}
}
